#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/3/7 8:52
# ===========================================
#       题目名称： 36. 有效的数独
#       题目地址： https://leetcode.cn/problems/valid-sudoku/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    def isValidSudoku(self, board):
        res_flag = True  # 判断是否ok
        # x 轴校验
        for i in range(len(board)):
            tmp_board = board[i]
            num_set = set()
            for tb in tmp_board:
                if tb != ".":
                    num_set_len = len(num_set)
                    num_set.add(tb)
                    if 0 < num_set_len == len(num_set):
                        res_flag = False
                        break
            if not res_flag:
                break
        # y 轴校验
        if res_flag:
            p = 0  # y 轴起始位置
            while p < len(board) and res_flag:
                num_set = set()
                for i in range(len(board)):
                    tb = board[i][p]
                    if tb != ".":
                        num_set_len = len(num_set)
                        num_set.add(tb)
                        if 0 < num_set_len == len(num_set):
                            res_flag = False
                            break
                p += 1
        # 3 * 3 校验
        if res_flag:
            # level_x , level_y x,y 初始层级 max_x max_y x,y 最大层级
            level_x, level_y, max_x, max_y = 0, 0, len(board) // 3, len(board[0]) // 3
            while level_x < max_x and res_flag:
                num_set = set()
                for i in range(3 * level_x, 3 * level_x + 3):
                    for j in range(3 * level_y, 3 * level_y + 3):
                        tb = board[i][j]
                        if tb != ".":
                            num_set_len = len(num_set)
                            num_set.add(tb)
                            if 0 < num_set_len == len(num_set):
                                res_flag = False
                                break
                    if not res_flag:
                        break
                if level_y + 1 >= max_y:
                    if level_x + 1 > max_x:
                        break
                    else:
                        level_x += 1
                        level_y = 0
                else:
                    level_y += 1

        return res_flag


if __name__ == "__main__":
    s = Solution()
    s1 = [
            ["5", "3", ".", ".", "7", ".", ".", ".", "."],
            ["6", ".", ".", "1", "9", "5", ".", ".", "."],
            [".", "9", "8", ".", ".", ".", ".", "6", "."],
            ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
            ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
            ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
            [".", "6", ".", ".", ".", ".", "2", "8", "."],
            [".", ".", ".", "4", "1", "9", ".", ".", "5"],
            [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ]

    print("s1 True=>", s.isValidSudoku(s1))

    s2 = [
            ["8", "3", ".", ".", "7", ".", ".", ".", "."],
            ["6", ".", ".", "1", "9", "5", ".", ".", "."],
            [".", "9", "8", ".", ".", ".", ".", "6", "."],
            ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
            ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
            ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
            [".", "6", ".", ".", ".", ".", "2", "8", "."],
            [".", ".", ".", "4", "1", "9", ".", ".", "5"],
            [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ]
    print("s2 False=>", s.isValidSudoku(s2))
